This page was automatically generated by NetLogo 5.0.4.
The applet requires Java 5 or higher. Java must be enabled in your browser settings. Mac users must have Mac OS X 10.4 or higher. Windows and Linux users may obtain the latest Java from Oracle's Java site.
In order for this to work, this file, your model file (Asynchronous Backtracking with a standard degree-based variable-ordering heuristic-brp.nlogo), and the files NetLogoLite.jar and NetLogoLite.jar.pack.gz must all be in the same directory. (You can copy NetLogoLite.jar and NetLogoLite.jar.pack.gz from the directory where you installed NetLogo.)
On some systems, you can test the applet locally on your computer before uploading it to a web server. It doesn't work on all systems, though, so if it doesn't work from your hard drive, please try uploading it to a web server.
You don't need to include everything in this file in your page. If you want, you can just take the HTML code beginning with <applet> and ending with </applet>, and paste it into any HTML file you want. It's even OK to put multiple <applet> tags on a single page.
If the NetLogoLite files and your model are in different directories, you must modify the archive= and value= lines in the HTML code to point to their actual locations. (For example, if you have multiple applets in different directories on the same web server, you may want to put a single copy of the NetLogoLite files in one central place and change the archive= lines of all the HTML files to point to that one central copy. This will save disk space for you and download time for your users.)
powered by NetLogo
view/download model file: Asynchronous Backtracking with a standard degree-based variable-ordering heuristic-brp.nlogo
Title: Random binary CSPs using Asynchronous Backtracking with a standard degree-based variable-ordering heuristic.
Author: Ionel Muscalagiu, Jose M. Vidal and Horia Popa
Description:
This is the implementation of the Asynchronous Backtracking algorithm for the random binary problems (SIES). The priority order among agents is determined with a standard degree-based variable-ordering heuristic. Variables are ordered before the start of the run of the search algorithm and the order is not changed during the run of the algorithm. The max-degree heuristic [Dechter 1988], orders the variables from last to first by selecting, at each stage, a node in the constraint graph which has a minimal degree in the graph remaining after deleting from the graph all nodes which have been selected already.We generate and solve the random binary problem using the Asynchronous Backtracking algorithm from
In generating a CSP (n, m,pl ,p2) exactly p1 * n * (n - 1)/2 constraints are randomly
selected (rounded to the nearest integer), and for each constraint selected exactly p2 * m*m conflicting pairs of values are selected (again, rounded to the nearest integer).
; Random binary CSPs using Asynchronous Backtracking with a standard degree-based variable-ordering heuristic.
; by Ionel Muscalagiu ( mionel@fih.upt.ro )
; Jose M. Vidal and Horia Popa
;The randomly generated (binary) CSPs are characterised by the 4-tuple (n, m,p1,p2),
;where n is the number of variables, m is the uniform domain size, p1 is the portion of
;the n * (n - 1) /2 possible constraints in the graph, and p2 is the portion of the m*m value
;pairs in each constraint that are disallowed by the constraint. That is, p1 may be thought
;of as the density of the constraint graph, and p2 as the tightness of constraints.
;In generating a CSP (n, m,pl ,p2) exactly p1 * n * (n - 1)/2 constraints are randomly
;selected (rounded to the nearest integer), and for each constraint selected exactly p2 * m*m conflicting pairs of values are selected (again, rounded to the nearest integer).
;
breed [ nodes ]
breed [ edges ]
breed [ weights ]
;nodes = agents
;each undirected edge goes from a to b
edges-own [a b weight-a weight-b wa-turtle wb-turtle number-of-edges ]
weights-own [sw1 sw2]
;the-links list of neighbor nodes (but the-links is a list of the 'who' of all nodes that have a constraint with me)
;the-neighbors the same but as an agentset
;neighbors-list is a list of the initial neighbors nodes
;done boolean that says if node (agent) is done or not
;message-queue contains the incoming messages. We take new ones out from the head.
;MyContext is a list indexed by node number [[color0 priority0] [color1 priority1] ...] colorl = -1 and priority = -1 if unknown.
;nogoods is a list of inconsistent colors [color0 color11 ... ]
;messages-recieved is the number of messages this vertice has received.
;nogood_list is the list of nogood received
;nogood_sent_list is the list of nogood sent
nodes-own [the-links neighbors-list the-neighbors message-queue priority nogood_list nogood_sent_list
ChildrenA ParentA MyValue_colorn MyContext nogoods messages-received_ok messages-received_nogood nr_constraintc
AgentC_Cost agent_nogood messages-received messages-received_nogoodold Forbidden_Pairs colorn childrenAExtended gt deg_n ]
globals [x-max y-max diam friction tot-edges filename tick1 stoptick init-power-edges domain-color-list
total-conflict-pairs no-more-messages done tmp nr_cicluri nn scris gata Orders]
__includes ["RBP.nls" "StaticOrders.nls"]
to setup-globals ; separate procedure for setting globals
let i 0
let max-edges 0
set diam 4
set tick1 0
set stoptick -2 ; set to some number to stop, generally for image collections
set x-max max-pxcor - (diam / 2) + 1; 0.5
set y-max max-pycor - (diam / 2) + 1; 0.5
set filename "" ; change to collect images (or just use command center after setup)
set-default-shape nodes "circle"
set-default-shape edges "line"
set friction .25
set init-power-edges 2
set max-edges round (number-of-variables * (number-of-variables - 1 ) / 2)
set tot-edges round (max-edges * p1-network-connectivity)
show (word "Muchii" tot-edges)
if tot-edges < number-of-variables - 1
[
set p1-network-connectivity precision ((number-of-variables - 1) / max-edges) 1
set tot-edges number-of-variables - 1
]
set domain-color-list []
set i 0
while [i < number-of-values][
set domain-color-list lput item i [15 105 64 125 45 85 35 55 5 12] domain-color-list
set i i + 1
]
end
to setup ; Setup the model for a run, build a graph.
clear-all
file-close
clear-output
set-default-shape weights "none"
setup-globals
setup-patches
setup-turtles
setup-random-binary-problems
;LoadGFile
;WriteGFile
;WriteColors;
CalculateOrdersMaxDegree
setup-ABTkernel
end
to setup-patches
ask patches [set pcolor white]
end
to setup-turtles
create-nodes number-of-variables [
set color one-of domain-color-list
;set color item (random-int-or-float num-colors) domain
set MyValue_colorn position color domain-color-list
set label-color black
set size diam
set the-links []
set label who
setxy random-float (x-max) * (2 * (random 2) - 1)
random-float (y-max) * (2 * (random 2) - 1)
]
end
to WriteSolution
show "Solution "
ask nodes [
write (word MyValue_colorn " ")
]
end
to-report verifica_solutia
let good 0
let i 0
set good true
;without-interruption[
ask nodes
[
without-interruption[
foreach neighbors-list
[
if Conflict who ? Myvalue_colorn [Myvalue_colorn] of turtle ?
[
set good false
show (word "Conflict " who " cu " ?)
]
]
]
]
if good
[show "Good solution!"]
report good
end
to WriteMasuratoriFisier
let tnogood 0
let tok 0
let tcc 0
let tcca 0
let nrcic 0
file-open FileS
set tnogood sum ([messages-received_nogood] of nodes)
set tok sum ([messages-received_ok] of nodes)
set tcc sum ( [nr_constraintc] of nodes)
set tcca max ( [AgentC_Cost] of nodes)
file-print (word tnogood " " tok " " tcc " " tcca " " nr_cicluri)
file-close
end
;;;;;;;;;;
;;;ABTkernel algorithm
;Initialize the ABT kernel algorithm +temprary link
to setup-ABTkernel
ask nodes [
set messages-received 0
set messages-received_ok 0
set messages-received_nogood 0
set messages-received_nogoodold 0
set nr_constraintc 0
set AgentC_Cost 0
set MyContext get-list number-of-variables -1
set nogoods get-list number-of-variables 0
set gt 0
set message-queue []
set-current-plot "Messages"
;create-temporary-plot-pen (word "n-" who)
; set-plot-pen-color (who * 10 + 5) mod 140
]
ask nodes [
ComputeParentA_ChildrenA
initialize
set childrenAExtended childrenA
;show (word who "-parinti " ParentA "-copii" ChildrenA)
]
set done false
set nr_cicluri 0
set gata false
set scris false
end
to ComputeParentA_ChildrenA
let i 0
set ChildrenA []
set ParentA []
;show the-neighbors
foreach neighbors-list
[
if (position ? Orders > position who Orders )
[set ChildrenA lput ? ChildrenA]
if (position ? Orders < position who Orders )
[set ParentA lput ? ParentA]
]
end
to go-ABTkernel
message-manage ;message-size
if (sum ([gt] of nodes ) = number-of-variables)
[ ;show gata
if not scris
[
if verifica_solutia
[show "Solution "
set scris true
;WriteSolution
;WriteMasuratoriFisier
stop
]
set scris true
stop
]
stop]
if (done)
[show "No solution"
stop]
end
to initialize
let msg 0
foreach childrenA
[
set msg (list "info" (list who MyValue_colorn) AgentC_Cost)
ask turtles with [who = ? ]
[receive-message msg]
]
end
;get the next message from message-queue
to-report retrieve-message
let msg 0
without-interruption [
set msg first message-queue
set message-queue butfirst message-queue]
report msg
end
to receive-message [msg]
without-interruption [
set message-queue lput msg message-queue]
end
to-report remove-old-info-message [xj]
let tip 0
let xjc 0
foreach message-queue
[
set tip first ?1
if (tip = "info" )
[
set xjc item 0 (item 1 ?)
if (xjc = xj )
[report 1]
]
]
report 0
end
to message-manage ;[ msize ] ; nodes proc
let n 0
let msg 0
let t 0
let nogoodset 0
let oldvalue 0
let xj 0
let dj 0
let msgNogood 0
let SenderC_Cost 0
let Sender 0
let tok 0
let tback 0
let tadd 0
set n 0
set nogoodset []
set tok false
set tback false
set tadd false
if (empty? message-queue) [
;set gata true
set gt 1
stop]
if not empty? message-queue
[
set gt 0
show message-queue
while [not empty? message-queue ]; and n < msize]
[
set msg retrieve-message
if (first msg = "stop")
[set gata true
stop
]
if (first msg = "info")
[
set xj item 0 (item 1 msg)
set messages-received_ok messages-received_ok + 1
set dj item 1 (item 1 msg)
set MyContext replace-item xj MyContext dj
set SenderC_Cost item 2 msg
if SenderC_Cost > AgentC_Cost
[
set AgentC_Cost SenderC_Cost
]
set tok true
]
if (first msg = "addl")
[
SetLink item 1 msg item 2 msg
set tadd true
]
if (first msg = "back")
[
set Sender item 2 msg
;if (remove-old-back-message Sender = 0 )
;[
set nogoodset lput msg nogoodset
set messages-received_nogood messages-received_nogood + 1
set msgNogood item 1 msg
set tback true
set SenderC_Cost item 3 msg
if SenderC_Cost > AgentC_Cost
[
set AgentC_Cost SenderC_Cost
]
ResolveConflict msgNogood Sender
;]
;[SendOklaBack item 1 msg item 2 msg]
]
set n n + 1
]
Set oldvalue MyValue_colorn
if tok = true and tback = false
[
UpdateContextInfo
CheckAgentView
]
if tok = true and tback = true
[
UpdateContextInfo
; foreach nogoodset
; [
; set msg ?
; set msgNogood item 1 msg
; set Sender item 2 msg
; ResolveConflict msgNogood Sender
; ]
CheckAgentView
]
if tok = false and tback = true
[
;UpdateContextInfo
; foreach nogoodset
; [
; set msg ?
; set msgNogood item 1 msg
; set Sender item 2 msg
; ResolveConflict msgNogood Sender
; ]
CheckAgentView1
]
SendInfolaBackFaraeEfect nogoodset oldvalue
]
end
to SendInfolaBackFaraeEfect [nogoodset oldvalue]
let msg 0
let msg1 0
let Sender 0
foreach nogoodset
[
set msg ?
set Sender item 2 msg
if ( oldValue = MyValue_colorn )
[
set msg1 (list "info" (list who MyValue_colorn) AgentC_Cost)
ask turtles with [who = Sender ]
[receive-message msg1]
]
]
end
to SendOklaBack [msgNogood Sender]
let msg 0
if ( (item who msgNogood = MyValue_colorn) );or (item who MsgNogood != -1 ))
[
;show "se trimite lui " + Sender
set msg (list "info" (list who MyValue_colorn) AgentC_Cost)
ask turtles with [who = Sender ]
[receive-message msg]
]
end
to ProcessInfo [msg ]
let xj 0
let dj 0
let SenderC_Cost 0
set xj item 0 (item 1 msg)
set dj item 1 (item 1 msg)
set SenderC_Cost item 2 msg
if SenderC_Cost > AgentC_Cost
[
set AgentC_Cost SenderC_Cost
]
;UpdateContextInfo xj dj
CheckAgentView
end
;this is the CheckAgentView procedure in the ABTkernel algorithm
to CheckAgentView
let TempValue 0
let msg 0
let tempc 0
if (not Is-Consistent);1 MyValue_colorn )
[
set TempValue ChooseValue
ifelse (TempValue > -1 )
[
set MyValue_colorn TempValue
;set color item MyValue_colorn domain-color-list
foreach childrenA
[
set msg (list "info" (list who MyValue_colorn) AgentC_Cost)
ask turtles with [who = ? ]
[receive-message msg]
]
]
[Backtrack]
]
end
to CheckAgentView1
let TempValue 0
let msg 0
let tempc 0
set TempValue ChooseValue
ifelse (TempValue > -1 )
[
set MyValue_colorn TempValue
;set color item MyValue_colorn domain-color-list
foreach childrenA
[
set msg (list "info" (list who MyValue_colorn) AgentC_Cost)
ask turtles with [who = ? ]
[receive-message msg]
]
]
[Backtrack]
end
to-report Conflict [who1 who2 value1 value2]
let result 0
let el 0
let pos 0
let element 0
set result false
if (neighbors? who1 who2)
[
set nr_constraintc nr_constraintc + 1
set AgentC_Cost AgentC_Cost + 1
ifelse who1 < who2
[
set el list value1 value2
set pos who1
;set pos position who1 ([neighbors-list] of turtle who2)
set element item pos ([Forbidden_Pairs] of turtle who2)
; show ([neighbors-list] of turtle who2)
]
[ set el list value2 value1
set pos who2
;set pos position who2 [neighbors-list] of turtle who1
set element item pos [Forbidden_Pairs] of turtle who1
;show ([neighbors-list] of turtle who1)
]
if element = []
[show "apare"
ifelse who1 < who2
[
;show (word "primul caz" who1 "-" value1 "," who2 "-" value2 "," el " - " element " " ([Forbidden_Pairs] of turtle who2))
]
[
;show (word "al doilea caz " pos " " who1 "-" value1 "," who2 "-" value2 "," el " - " element " " ([Forbidden_Pairs] of turtle who1))
]
]
;show (word who1 "-" value1 "," who2 "-" value2 "," el " - " element)
if (member? el element )
[set result true]
]
report result
end
to UpdateContextInfo
let i 0
let j 0
; set MyContext replace-item Qj MyContext Vj
;set i Qj
set nogoods get-list number-of-values 0
set i 0
while [ i < number-of-variables] ;for each vertice
[set j 0
while [ j < number-of-values] ;for each color
[
;set nr_constraintc nr_constraintc + 1
;set AgentC_Cost AgentC_Cost + 1
; if ((neighbors? i who) and ( j = (item i MyContext)) and (item i MyContext != -1 ))
if (position i Orders < position who Orders) and (item i MyContext != -1 ) and (Conflict who i j item i MyContext)
[set nogoods replace-item j nogoods 1]
set j (j + 1)]
set i (i + 1)]
end
to SetLink [Dest Sender]
let msg 0
if not member? Sender childrenAExtended
[ ;show Sender
set childrenA lput Sender childrenA
set childrenA sort childrenA
set msg (list "info" (list who MyValue_colorn) AgentC_Cost)
ask turtles with [who = Sender ]
[receive-message msg]
]
end
to CheckAddLink [msgNogood]
let i 0
let msg 0
;show msgNogood
set i 0
while [i < number-of-variables]
[
if ((item i msgNogood) != -1) and (not member? i ParentA) and (position i Orders < position who Orders)
[
set ParentA lput i ParentA
set ParentA sort ParentA
set MyContext (replace-item i MyContext (item i msgNogood))
set msg (list "addl" i who )
ask turtles with [who = i ]
[receive-message msg]
]
set i (i + 1)
]
end
to-report Is-Consistent
let i 0
let consistent 0
set consistent true
if (item MyValue_colorn nogoods = 1)
[
set consistent false
]
report consistent
end
to-report Is-Consistent1 [value_colorn]
let i 0
let consistent 0
set consistent true
set i 0
while [ i < number-of-variables ] ;for each vertice
[
;set nr_constraintc nr_constraintc + 1
;set AgentC_Cost AgentC_Cost + 1
;if ((item i MyContext != -1 ) and (neighbors? i who) and ( Value_colorn = (item i MyContext)))
if ((item i MyContext != -1 ) and Conflict who i Value_colorn item i MyContext) and (position i Orders < position who Orders)
[
set consistent false
]
set i i + 1
]
report consistent
end
;this is the Coherent function in the ABTkernel algorithm
to-report Is-obsolete [msgNogood Sender]
let i 0
let res 0
set i 0
set res false
while [i < number-of-variables]
[if ((item i MsgNogood != -1 ) and (item i MyContext != -1 ) and (item i msgNogood) != (item i MyContext) and member? i ParentA) and (position i Orders < position who Orders)
; [if ((item i msgNogood) != (item i MyContext) and member? i ParentA)
[set res true]
set i (i + 1)]
if ( (item who MsgNogood != -1 ) and ((item who msgNogood) != MyValue_colorn))
;if ( ((item who msgNogood) != MyValue_colorn))
[set res true]
report res
end
;this is the Coherent function in the ABTkernel algorithm
to-report Is-Coherent [msgNogood Sender]
let i 0
let res 0
set res true
foreach ParentA
[
set i ?
if ((item i MsgNogood != -1 ) and (item i MyContext != -1 ) and (item i msgNogood) != (item i MyContext))
; [if ((item i msgNogood) != (item i MyContext) and member? i ParentA)
[set res false]
]
if ( (item who MsgNogood != -1 ) and ((item who msgNogood) != MyValue_colorn))
; if ( ((item who msgNogood) != MyValue_colorn))
[set res false]
report res
end
to ResolveConflict [msgNogood Sender]
let i 0
let j 0
let msg 0
let TempValue 0
;if it is consistent with the agent view, otherwise it is discarded due to obsolescence.
ifelse ( Is-Coherent msgNogood Sender)
;An accepted nogood is used to update the agent view of agents not in PArentA
;Update MyContext
[CheckAddLink msgNogood
;UpdateContextNogood
;The nogood is stored
set nogoods replace-item MyValue_colorn nogoods 1 ;mark current position as nogood
CheckAgentView1
]
[ set messages-received_nogoodold messages-received_nogoodold + 1
; if (member? Sender childrenA) and ( (item who msgNogood = MyValue_colorn)); or (item who MsgNogood != -1 ))
if ( (item who msgNogood = MyValue_colorn)); or (item who MsgNogood != -1 )
[
;show "se trimite lui " + Sender
set msg (list "info" (list who MyValue_colorn) AgentC_Cost)
ask turtles with [who = Sender ]
[receive-message msg]
]
]
end
to-report agents-in-context [cont]
let i 0
let res 0
set i 0
set res []
while [i < number-of-variables]
[
if (item i cont != -1) and (item (item i cont) nogoods) = 1 and (position i Orders < position who Orders) and member? i parentA ; and (position i Orders < position who Orders)
[
set res lput i res
]
set i i + 1
]
report res
end
to-report Close-Agent [cont]
let el []
let mina number-of-variables
let pos position who Orders
let ag -1
foreach cont
[
set el ?
if (abs (pos - position el Orders)) < mina
[set mina abs (pos - position el Orders)
set ag ?]
]
;show (word pos " " cont " " ag)
report ag
end
;;this is the BackTrack procedure in the ABT algorithm
to BackTrack
let msg 0
let i 0
let j 0
let wng 0
let m 0
let newNogood 0
let LAgents 0
set LAgents agents-in-context MyContext
ifelse empty? LAgents ;newNogood=empty;
[
show ( word "No solution" who)
set done true
set msg "stop"
receive-message msg
stop
]
[
;set wng last Lagents
set wng Close-Agent Lagents
set newNogood MyContext
set m item wng MyContext
set i 0
while [i < number-of-variables ]
[ if (item i newNogood != -1) and (item (item i newNogood) nogoods = 0 ) and (position i Orders < position who Orders)
[
set newNogood (replace-item i newNogood -1) ]
set i i + 1
]
set msg (list "back" newNogood who AgentC_Cost )
ask turtles with [who = wng ]
[receive-message msg]
set MyContext (replace-item wng MyContext -1)
UpdateContextConflict
UpdateContextConflict1 m
CheckAgentView1
]
end
to UpdateContextConflict1 [culors]
let i 0
let j 0
let msg 0
let TempValue 0
set nogoods replace-item culors nogoods 0
set i 0
while [ i < number-of-variables ] ;for each vertice
[
;set nr_constraintc nr_constraintc + 1
; set AgentC_Cost AgentC_Cost + 1
; if ((neighbors? i who) and ( culors = (item i MyContext)) and (item i MyContext != -1 ))
if ( (item i MyContext != -1 ) and Conflict who i culors item i MyContext) and (position i Orders < position who Orders)
[set nogoods replace-item culors nogoods 1]
set i (i + 1)
]
end
to UpdateContextNogood
let i 0
let j 0
set nogoods get-list number-of-values 0
set i 0
while [ i < number-of-variables ] ;for each vertice
[set j 0
while [ j < number-of-values] ;for each color
[;
;set nr_constraintc nr_constraintc + 1
;if ((neighbors? i who) and ( j = (item i MyContext)) and (item i MyContext != -1 ))
if (item i MyContext != -1 ) and (Conflict who i j item i MyContext) and (position i Orders < position who Orders)
[set nogoods replace-item j nogoods 1]
set j (j + 1)]
set i (i + 1)]
end
to UpdateContextConflict
let i 0
let j 0
set nogoods get-list number-of-values 0
set i 0
while [ i < number-of-variables ] ;for each vertice
[set j 0
while [ j < number-of-values] ;for each color
[
;set nr_constraintc nr_constraintc + 1
;set AgentC_Cost AgentC_Cost + 1
if (item i MyContext != -1 ) and (Conflict who i j item i MyContext) and (position i Orders < position who Orders)
[set nogoods replace-item j nogoods 1]
set j (j + 1)]
set i (i + 1)]
end
to-report ChooseValue
let i 0
let j 0
set i 0
set j 0
while [ i < number-of-values and j = 0]
[if ( item i nogoods = 0 )
[
ifelse Is-Consistent1 i
[set j 1
report i
]
[
set nogoods replace-item i nogoods 1
]
]
set i (i + 1)]
; setxy (i - screen-edge-x) (screen-edge-y - who)
report -1
end
to-report ChooseValue1
let i 0
let j 0
set i 0
set j 0
while [ i < number-of-values and j = 0]
[if ( item i nogoods = 0 )
[
set j 1
report i
]
set i (i + 1)]
; setxy (i - screen-edge-x) (screen-edge-y - who)
report -1
end
to-report neighbors? [v1 v2]
report (member? v2 [neighbors-list] of turtle v1) or (member? v1 [neighbors-list] of turtle v2)
end